package leetcode_100;

import java.util.Arrays;

/**
 *@author 周杨
 *MultiplyStrings_43 Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"
Example 2:

Input: num1 = "123", num2 = "456"
Output: "56088"
 *describe: 下标i和下标j相乘的高位结果位于下标i+j处，低位位于下标i+j+1处
 *2018年5月4日 下午1:11:31
 */
public class MultiplyStrings_43 {

	public static void main(String[] args) {
		System.out.println(multiply("0", "45"));

	}
	public static String multiply(String num1, String num2) {
		if(num1.equals("0")||num2.equals("0"))
			return "0";
        int [] res=new int[num1.length()+num2.length()];
        for(int i=0;i<num2.length();++i) {
        	for(int j=0;j<num1.length();++j) {
        		int k=(num1.charAt(j)-'0')*(num2.charAt(i)-'0');
        		int index0=k%10;//低位
        		int index1=k/10;//高位
        		add(res,i+j+1,index0);
        		add(res,i+j,index1);
        	}
        }
        int count=0;
        while(res[count]==0)
        	++count;
        StringBuffer sb=new StringBuffer();
        for(int i=count;i<res.length;++i)
        	sb.append(res[i]);
        return sb.toString();
    }
	
	public static void add(int []res,int index,int sum) {
		if(res[index]+sum>=10) {
			res[index]=(res[index]+sum)%10;
			add(res,index-1,1);
		}
		else{
			res[index]+=sum;
		}
	}

}
